﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using System.Threading.Tasks;


class Sol10
{



    // Regular Expression
    public bool regex2(string s, string p)
    {
        int lenS = s.Length;
        int lenp = p.Length;

        Console.WriteLine(lenp);
        if (lenS == 0)
        {
            return true;
        }
        bool[][] isMatch = new bool[lenS + 1][];
        for (int i = 0; i <= lenS; i++)
        {
            isMatch[i] = new bool[lenp + 1];
        }

        //边界条件, 两个空字符串

        isMatch[0][0] = true;


        for (int i = 0; i <= lenS; i++)
        {


            for (int j = 1; j <= lenp; j++)
            {



                if (myMatch(s, p, i, j))
                {//匹配有两种情况，p[j]和s[i]一样，或者p[j]为.

                    isMatch[i][j] = isMatch[i - 1][j - 1];
                }
                //不匹配有两种情况，p[j]和s[i]不一样，p[j]为*。这个时候看前面

                else
                {
                    if (p[j] != '*')
                    {
                        return false;
                    }
                    else//p[j] == '*'
                    {
                        //看p[j-1] == s[i]相等，p[j-1]不一定是a，也可能是*表示的，不过无所谓


                        if (myMatch(s, p, i, j - 1))
                        {
                            isMatch[i][j] = true;
                        }
                        else
                        {
                            return false;
                        }

                    }

                }






            }



        }

        return isMatch[lenS - 1][lenp - 1];
    }
    public bool IsMatch(string s, string p)//官方写法，有一点难懂
    {
        int lenS = s.Length;
        int lenp = p.Length;


        bool[][] isMatch = new bool[lenS + 1][];
        for (int i = 0; i <= lenS; i++)
        {
            isMatch[i] = new bool[lenp + 1];
        }

        //边界条件, 两个空字符串

        isMatch[0][0] = true;


        for (int i = 0; i <= lenS; i++)//这个i和j是isMatch的索引
        {


            for (int j = 1; j <= lenp; j++)
            {

                //不匹配有两种情况，p[j]和s[i]不一样，p[j]为*。这个时候看前面


                if (p[j - 1] != '*')
                {
                    if (myMatch(s, p, i, j))
                    {//匹配有两种情况，p[j]和s[i]一样，或者p[j]为.

                        isMatch[i][j] = isMatch[i - 1][j - 1];
                    }
                    //不匹配什么事情也不做，
                    //isMatch[i][j] = false，其实应该是false，但是初始化就是fasle了

                }
                else//p[j - 1] == '*'
                {
                    //看p[j-1] == s[i]相等，p[j-1]不一定是a，也可能是*表示的，不过无所谓
                    

                    if (myMatch(s, p, i, j - 1))//匹配0个成功，扔掉组合（字母 + 星号的组合）或者s 末尾的一个字符，将该字符扔掉
                    {
                        isMatch[i][j] = isMatch[i][j - 2] || isMatch[i - 1][j];
                        //j-2或者i-1都可以，j-2代表去掉a+*，
                        //i-1代表去匹配 s 末尾的一个字符，将该字符扔掉，而该组合（字母 + 星号的组合）还可以继续进行匹配
                    }
                    else
                    {
                        //在匹配 0 次的情况下，一个字符 + 星号的组合
                        isMatch[i][j] = isMatch[i][j - 2];//值已经更新了，p[j - 1] == '*',看p[j - 2] == 'b'是否匹配  
                    }




                }






            }



        }

        return isMatch[lenS][lenp];
    }
    bool myMatch(string s, string p, int i, int j)//这个i和j是isMatch的索引，由于isMatch[0][0]=true;被空字符占用了，所以在使用ij取字符串的值的时候需要-1
    {
        if (i == 0) { return false; }//没法取0-1
        if (p[j - 1] == '.') { return true; }
        return p[j - 1] == s[i - 1];

    }




    //默写一遍
    public bool regex(string s,string p)
    {
        int m=s.Length;
        int n=p.Length;


        bool[][] isMatch = new bool[m+1][];
        for (int i = 0; i <= m; i++)
        {
            isMatch[i]=new bool[n+1];
        }

        isMatch[0][0]=true; 
        for(int i = 0; i <= m; i++)
        {

            for(int j = 1; j <= n; j++)
            {


                if (p[j - 1] == '*')
                {

                    if (myMatch2(s, p, i, j-1))//遇到*，看前一个字母
                    {

                        //匹配，看前两个或者s的前一个

                        isMatch[i][j] = isMatch[i - 1][j ]|| isMatch[i][j-2];//选择

                    }
                    else{
                        isMatch[i][j] =  isMatch[i][j - 2];
                    }

                }
                else
                {
                    if (myMatch2(s, p, i, j))
                    {

                        isMatch[i][j] = isMatch[i-1][j-1];


                    }
                }
             



            }
           
        }
        return isMatch[m][n];
    }

    private bool myMatch2(string s, string p, int i, int j)
    {
        if (i == 0)
        {
            return false;
        }
        if (p[j-1] == '.')
        {
            return true;
        }
        return s[i-1] == p[j-1];
    }
}

class Program10
{
    static void Main10(string[] args)
    {


        string s = "aa";
        string p = "a*";
        //string s = "aa";
        //string p = "a"; 
        //string s = "ab";
        //string p = ".*";
        Sol10 sol = new Sol10();
        //bool res = sol.IsMatch(s, p);
        bool res = sol.regex(s, p);
        Console.WriteLine(res);
    }
}